#include <iostream>
#include <cstdio>
#include <conio.h>
#include <cstdlib>
#include <cassert>
#include <queue>
#include <deque>
#include <windows.h>
#include <ctime>
using namespace std;
enum faction {down, up, lleft, rright};
enum moving {got, failed, success};

const char s_null = ' ';
const char s_wall = 'X';
const char s_food = 'O';
const char s_snake = 'C';

int score = 0;

struct snake {
	int x, y, f;
	snake *next, *prev;
};

struct BaseMap {

	const int HEIGHT, WEIGHT;

	char map[2048][2048];

	BaseMap(int h, int w) : HEIGHT(h), WEIGHT(w) {
		srand((unsigned int)time(NULL));
		reset();
	}

	void reset() {
		for (int i=0; i<=HEIGHT+1; ++i)
			map[i][0] = map[i][WEIGHT+1] = s_wall;
		for (int i=0; i<=WEIGHT+1; ++i)
			map[0][i] = map[HEIGHT+1][i] = s_wall;
		for (int i=1; i<=HEIGHT; ++i)
			for (int j=1; j<=WEIGHT; ++j)
				map[i][j] = s_null;
	}

	void paint() {
		system("cls");
		printf("Score: %d\n", score);
		for (int i=0; i<=HEIGHT+1; ++i) {
			for (int j=0; j<=WEIGHT+1; ++j)
				printf("%c", map[i][j]);
			printf("\n");
		}
	}

	void move(snake** head, snake** rear) {
		map[(*rear)->x][(*rear)->y] = s_null;
		(*rear)->x = (*head)->x;
		(*rear)->y = (*head)->y;
		
		snake* moved = (*rear);

		*rear = moved->prev;
		(*rear)->next->prev = NULL;
		(*rear)->next = NULL;
	
		(*head)->prev = moved;
		moved->next = (*head);
		*head = moved;
	
		switch(moved->next->f) {
			case down: moved->x += 1; break;
			case up: moved->x -= 1; break;
			case rright: moved->y += 1; break;
			case lleft: moved->y -= 1; break;
		}
		map[moved->x][moved->y] = s_snake;
		moved->f = moved->next->f;
	}

	int addin(snake** head, snake** rear) {
		snake* newp = new snake();
		newp->prev = *rear;
		(*rear)->next = newp;
		newp->x = newp->prev->x;
		newp->y = newp->prev->y;
		newp->f = newp->prev->f;
		newp->next = NULL;
		*rear = newp;
		switch (newp->f) {
			case down: 
				if (map[newp->x-1][newp->y] != s_snake && map[newp->x-1][newp->y] != s_wall) {
					newp->x -= 1; break;
				}
			case up:
				if (map[newp->x+1][newp->y] != s_snake && map[newp->x+1][newp->y] != s_wall) {
					newp->x += 1; break;
				}
			case lleft:
				if (map[newp->x][newp->y+1] != s_snake && map[newp->x][newp->y+1] != s_wall) {
					newp->y += 1; break;
				}
			case rright:
				if (map[newp->x][newp->y-1] != s_snake && map[newp->x][newp->y-1] != s_wall) {
					newp->y -= 1; break;
				}
			default: {
				return failed;
			}
		}
		return got;
	}
		
	int moveSnake(snake** head, snake** rear) {
		int x = (*head)->x, y = (*head)->y;
		switch ((*head)->f) {
			case down: x += 1; break;
			case up: x -= 1; break;
			case rright: y += 1; break;
			case lleft: y -= 1; break;
		}
		if (map[x][y] == s_wall || map[x][y] == s_snake) {
			return failed;
		} else if (map[x][y] == s_food) {
			move(head, rear);
			return addin(head, rear);
		} else {
			move(head, rear);
			return success;
		}
	}

	void spawnfood(snake* head) {
		int x, y;
		do {
			x = rand() %HEIGHT+1;
			y = rand() %WEIGHT+1;
		} while (map[x][y] == s_snake);
		map[x][y] = s_food;
	}

};

void drop_list(snake* head) {
	if (head != NULL) {
		drop_list(head->next);
		delete head;
	}
}

snake* spawnsnake(int h, int w) {
	snake* p = new snake();
	p->x = rand() % (h/2) + h/4;
	p->y = rand() % (w/2) + w/4;
	p->f = down;
	int dis = h-1-p->x;
	if (p->x-1 > dis) p->f = up;
	if (p->y-1 > dis) p->f = lleft;
	if (w-1-p->y > dis) p->f = rright;
	p->next = p->prev = NULL;
	return p;
}

int main() {
	printf("Welcome to Greedy Snake\n");
	printf("Press any key to continue\n");
	int tmp = getch();

	BaseMap* map_ptr = new BaseMap(32,32);
	snake* head = spawnsnake(map_ptr->HEIGHT, map_ptr->WEIGHT), *rear = head;
	map_ptr->map[head->x][head->y] = s_snake;
	map_ptr->spawnfood(head);

	while (true) {
		int fgot=getch(); // ...
		head->f = fgot;
		map_ptr->paint();
		switch (map_ptr->moveSnake(&head, &rear)) {
			case success: break;
			case failed: 
				system("cls");
				printf("Score: %d\n", score);
				printf("Oh, sorry, you lost!\n");
				goto out;
			case got:
				score += 1;
				map_ptr->spawnfood(head);
		}
		Sleep(400);
	}

out:drop_list(head);
	delete map_ptr;
	delete head;
	system("pause");
	return 0;
}
